from itertools import count
from functools import cache

# 已知最小操作次数去推导楼层

# 定义一个递归函数 dfs，使用 @cache 装饰器实现记忆化搜索，避免重复计算
# i 表示尝试的次数，j 表示鸡蛋的数量
@cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int) -> int:
    # 当尝试次数为 0 或者鸡蛋数量为 0 时，能确定的楼层数为 0
    if i == 0 or j == 0:
        return 0
    # 递归计算在 i 次尝试和 j 个鸡蛋的情况下能确定的最大楼层数
    # dfs(i - 1, j) 表示在第 i 次尝试时鸡蛋没碎，还剩 i - 1 次尝试和 j 个鸡蛋能确定的楼层数
    # dfs(i - 1, j - 1) 表示在第 i 次尝试时鸡蛋碎了，还剩 i - 1 次尝试和 j - 1 个鸡蛋能确定的楼层数
    # 加上 1 是因为当前这次尝试可以确定一层楼
    return dfs(i - 1, j) + dfs(i - 1, j - 1) + 1

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # 使用 count(1) 从 1 开始无限枚举尝试次数 i
        for i in count(1):  # 从 1 开始枚举 i
            # 调用 dfs 函数计算在 i 次尝试和 k 个鸡蛋的情况下能确定的最大楼层数
            # 如果这个最大楼层数大于等于给定的楼层数 n
            if dfs(i, k) >= n:
                # 则当前的尝试次数 i 就是最少需要的尝试次数，将其返回
                return i


# 动态规划
from itertools import count

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # 创建一个二维数组 f，用于存储在不同尝试次数和不同鸡蛋数量下能确定的最大楼层数
        # f[i][j] 表示使用 i 次尝试和 j 个鸡蛋时能确定的最大楼层数
        # 初始化数组的大小为 (n + 1) 行和 (k + 1) 列，初始值都为 0
        f = [[0] * (k + 1) for _ in range(n + 1)]

        # 使用 count(1) 从 1 开始无限枚举尝试次数 i
        for i in count(1):  # 从 1 开始枚举 i
            # 遍历鸡蛋数量，从 1 到 k
            for j in range(1, k + 1):
                # 状态转移方程，计算在 i 次尝试和 j 个鸡蛋的情况下能确定的最大楼层数
                # f[i - 1][j] 表示在第 i 次尝试时鸡蛋没碎，还剩 i - 1 次尝试和 j 个鸡蛋能确定的楼层数
                # f[i - 1][j - 1] 表示在第 i 次尝试时鸡蛋碎了，还剩 i - 1 次尝试和 j - 1 个鸡蛋能确定的楼层数
                # 加上 1 是因为当前这次尝试可以确定一层楼
                f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + 1
            # 检查使用 i 次尝试和 k 个鸡蛋时能确定的最大楼层数是否大于等于给定的楼层数 n
            if f[i][k] >= n:
                # 如果满足条件，说明当前的尝试次数 i 就是最少需要的尝试次数，将其返回
                return i